﻿/*
 * 由SharpDevelop创建。
 * 用户： Joy
 * 日期: 2013/9/23
 * 时间: 23:49
 * 
 * 要改变这种模板请点击 工具|选项|代码编写|编辑标准头文件
 */
using System;
using System.Collections.Generic;

namespace LongestCommonSubsequence
{
    /// <summary>
    /// Description of LongestCommonSequence.
    /// </summary>
    public class LongestCommonSubsequence
    {
        private enum Direction
        {
            Left,
            Up,
            UpLeft,
            UpOrLeft,
            End,
            Null
        }
        public String X { get; set; }
        public String Y { get; set; }

        private class Position : Tuple<Int32, Int32, Boolean>
        {
            public Position(Int32 x, Int32 y, Boolean newLCS)
                : base(x, y, newLCS)
            {

            }
            public Position(Int32 x, Int32 y)
                : base(x, y, false)
            {

            }
            public Int32 X
            {
                get
                {
                    return Item1;
                }
            }
            public Int32 Y
            {
                get
                {
                    return Item2;
                }
            }
            public Boolean NewLCS
            {
                get
                {
                    return Item3;
                }
            }
        }



        public String[] CalculateLongestCommonSequence()
        {
            Int32[,] c = new Int32[X.Length, Y.Length];
            Direction[,] d = new Direction[X.Length, Y.Length];
            #region Calculate matrix c & d
            for (int i = 0; i < X.Length; i++)
            {
                for (int j = 0; j < Y.Length; j++)
                {
                    if (i == 0 || j == 0)
                    {
                        if (X[i] == Y[j])
                        {
                            c[i, j] = 1;
                            d[i, j] = Direction.End;
                        }
                        else if (i > 0)
                        {
                            c[i, j] = c[i - 1, j];
                            d[i, j] = Direction.Left;

                        }
                        else if (j > 0)
                        {
                            c[i, j] = c[i, j - 1];
                            d[i, j] = Direction.Up;
                        }
                        else
                        {
                            c[i, j] = 0;
                            d[i, j] = Direction.Null;
                        }

                    }
                    else
                    {
                        if (X[i] == Y[j])
                        {
                            c[i, j] = c[i - 1, j - 1] + 1;
                            if (c[i, j] == 1)
                                d[i, j] = Direction.End;
                            else
                                d[i, j] = Direction.UpLeft;
                        }
                        else
                        {
                            if (c[i - 1, j] > c[i, j - 1])
                            {
                                c[i, j] = c[i - 1, j];
                                d[i, j] = Direction.Left;
                            }
                            else if (c[i - 1, j] == c[i, j - 1])
                            {
                                c[i, j] = c[i - 1, j];
                                d[i, j] = Direction.UpOrLeft;
                            }
                            else if (c[i - 1, j] < c[i, j - 1])
                            {
                                c[i, j] = c[i, j - 1];
                                d[i, j] = Direction.Up;
                            }
                        }
                    }

                }
            }
            #endregion



            #region DFS the graph and enumerate all result
            Boolean[,] access = new Boolean[X.Length, Y.Length];
            for (Int32 i = 0; i < X.Length; i++)
            {
                for (Int32 j = 0; j < Y.Length; j++)
                {
                    access[i, j] = false;
                }
            }


            Position start = new Position(X.Length - 1, Y.Length - 1, true);
            List<String> result = new List<String>();
            Char[] oneLCS = new Char[c[start.X, start.Y]];
            Int32 iOneLCS = 0;
            Int32 flag = c[start.X, start.Y];
            Stack<Position> s = new Stack<Position>();

            s.Push(start);
            while (s.Count > 0)
            {
                Position position = s.Pop();
                iOneLCS = c[position.X, position.Y] - 1;
                access[position.X, position.Y] = true;
                switch (d[position.X, position.Y])
                {
                    case Direction.Left:
                        s.Push(new Position(position.X - 1, position.Y, position.NewLCS));


                        break;
                    case Direction.Up:
                        if (!access[position.X, position.Y - 1])
                        {
                            s.Push(new Position(position.X, position.Y - 1, position.NewLCS));

                        }
                        else if (position.NewLCS)
                        {
                            s.Push(new Position(position.X, position.Y - 1, position.NewLCS));
                            for (Int32 i = 0; i <= position.X; i++)
                            {
                                for (Int32 j = 0; j <= position.Y - 1; j++)
                                {
                                    access[i, j] = false;
                                }
                            }
                        }
                        break;
                    case Direction.UpLeft:

                        oneLCS[iOneLCS] = X[position.X];
                        s.Push(new Position(position.X - 1, position.Y - 1, true));
                        break;
                    case Direction.UpOrLeft:

                        s.Push(new Position(position.X - 1, position.Y, false));

                        if (!access[position.X, position.Y - 1])
                        {
                            s.Push(new Position(position.X, position.Y - 1, position.NewLCS));

                        }
                        else if (position.NewLCS)
                        {
                            s.Push(new Position(position.X, position.Y - 1, position.NewLCS));
                            for (Int32 i = 0; i <= position.X; i++)
                            {
                                for (Int32 j = 0; j <= position.Y - 1; j++)
                                {
                                    access[i, j] = false;
                                }
                            }
                        }
                        break;
                    case Direction.End:
                        oneLCS[iOneLCS] = X[position.X];
                        result.Add(new String(oneLCS));

                        break;
                    case Direction.Null:
                        break;
                    default:
                        throw new Exception("Wrong position");
                }

            }
            #endregion


            return result.ToArray();
        }



    }
}
